#include "SearchBinaryTree.h"
void SearchBinaryTree_Key()
{
    int a[] = {8,3,1,10,6,4,7,14,13};
    key::BSTree<int> t;
    for(int i = 0;i < 9;i++)
    {
        t.Insert(a[i]);
    }
    t.InOrder();
    t.Erase(8);
    t.InOrder();
    t.Erase(14);
    t.InOrder();
    t.Erase(1);
    t.InOrder();
    for(auto e : a)
    {
        t.Erase(e);
        t.InOrder();
    }
    
}
void SearchBinaryTree_Key_Val()
{
    int a[] = {8,3,1,10,6,4,7,14,13};
    key_value::BSTree<int,int> t;
    for(auto e : a)
    {
        t.Insert(e,e);
    }
    t.InOrder();
    t.Erase(8);
    t.InOrder();
    t.Erase(14);
    t.InOrder();
    t.Erase(1);
    t.InOrder();
    for(auto e : a)
    {
        t.Erase(e);
        t.InOrder();
    }
}
void CountTest()
{
    //统计次数
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    key_value::BSTree<string,int> countTree;
    for(const auto& e : arr)
    {
        key_value::BSTNode<string,int>* ret = countTree.Find(e);
        //auto ret = countTree.Find(e);
        if(ret == nullptr)
        {
            countTree.Insert(e,1);
        }
        else
        {
            ret->_val++;
        }
    }
    countTree.InOrder();
}
int main()
{
     SearchBinaryTree_Key();
     cout << "*******************************" << endl;
     SearchBinaryTree_Key_Val();
    //CountTest();
    return 0;
}
/*
2025.1.18 假期补课打卡第九天 二叉搜索树
二叉搜索树是用来查找数据的,也可以顺便排个序,但是主要功能
还是用来查找,每个结点左孩子比根结点小,右孩子比根结点大,
所以在我们中序遍历的时候就是升序,查找的时候也是一样,比
根结点小那就去左边查找,比根结点大那么就去右边查找,最多
只需查找高度次就可以了,但是这个树也有可能退化为单只树,
这个也就根我们插入数据的顺序有关系了,所以就会有另一个数
据结构,平衡二叉搜索树,让两端的结点高度平衡。
我们可以发现,二叉搜索树的效率和二分查找的的
时间复杂度也是一样,但是二分查找要排序,其实也不影响,用
不了多长时间,就是插入和删除效率很低,需要挪动数据,二叉
搜索树支持插入,删除,查找,不支持修改,修改了就不是一颗二
叉搜索树了,也就是说这个树也就没有任何价值了。
*/